package org.usmile.algorithms.huawei.acm;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// https://blog.csdn.net/qq_34465338/article/details/128603820
public class _硬件产品销售方案 {
    private static int amount;
    private static int[] prices;
    private static final List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        amount = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        String[] pricesStr = str.substring(1, str.length() - 1).split(",");
        prices = new int[pricesStr.length];
        for (int i = 0; i < prices.length; i++) {
            prices[i] = Integer.parseInt(pricesStr[i]);
        }
        dfs(0, new ArrayList<>(), 0);

        System.out.println(result);
    }

    private static void dfs(int index, List<Integer> path, int total) {
        if (total >= amount) {
            if (total == amount) {
                result.add(new ArrayList<>(path));
            }

            return;
        }

        for (int i = index; i < prices.length; i++) {
            path.add(prices[i]);
            dfs(i, path, total + prices[i]);
            path.remove(path.size() - 1);
        }
    }
}
